/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class NumberofSubarrayswithBoundedMaximum {
	public int numSubarrayBoundedMax(int[] A, int L, int R) {
		int i = 0;
		int res = 0;
		while (i < A.length) {
			while (i < A.length && A[i] > R) {
				i++;
			}
			int start = i;
			while (i < A.length && A[i] <= R) {
				int last0 = i;
				int lessCount = 0;
				// 数<L的个数
				while (i < A.length && A[i] < L) {
					i++;
					lessCount++;
				}
				while (i < A.length && A[i] >= L && A[i] <= R) {
					res += (i - start) + 1;// 对于[L,R]的元素，能和前面所有子序列进行组合.+1代表不进行组合，1个元素的数组
					i++;
				}
				if (lessCount != 0) {
					res += (last0 - start) * (lessCount);
				}
			}
		}
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] A = { 73, 55, 36, 5, 55, 14, 9, 7, 72, 52 };
		int L = 32;
		int R = 69;
		System.out.println(new NumberofSubarrayswithBoundedMaximum().numSubarrayBoundedMax(A, L, R));
	}

}
